package leetcode11;

public class test62 {
    /**
     * 33. 搜索旋转排序数组
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;

        // 当左指针小于等于右指针时继续搜索
        while (left <= right) {
            // 计算中间索引，避免直接加法导致溢出
            int mid = left + (right - left) / 2;

            // 如果目标值等于中间值，返回中间索引
            if (nums[mid] == target) return mid;

            // 检查左半部分是否有序
            if (nums[mid] > nums[right]) {
                // 如果目标值在左半部分范围内
                if (nums[mid] > target) {
                    // 如果目标值小于最左边的值，目标必在右半部分
                    if (nums[left] > target) {
                        left = mid + 1; // 移动左指针到中间位置的右边
                    } else {
                        right = mid - 1; // 移动右指针到中间位置的左边
                    }
                } else {
                    left = mid + 1; // 移动左指针到中间位置的右边
                }
            } else {
                // 右半部分有序
                if (nums[mid] < target) {
                    // 如果目标值大于最右边的值，目标必在左半部分
                    if (nums[right] < target) {
                        right = mid - 1; // 移动右指针到中间位置的左边
                    } else {
                        left = mid + 1; // 移动左指针到中间位置的右边
                    }
                } else {
                    right = mid - 1; // 移动右指针到中间位置的左边
                }
            }
        }

        // 如果没有找到目标值，返回 -1
        return -1;
    }

}
